Human cathepsin B has many house-keeping functions, such as protein turnover in lysosomes. However, dysregulation of its activity is associated with numerous diseases, including cancers. We present here the structure-based design and synthesis of new cathepsin B inhibitors using the cocrystal structure of 5-nitro-8-hydroxyquinoline in the cathepsin B active site. A focused library of over 50 compounds was prepared by modifying positions 5, 7, and 8 of the parent compound nitroxoline. The kinetic parameters and modes of inhibition were characterized, and the selectivities of the most promising inhibitors were determined. The best performing inhibitor 17 was effective in cell-based in vitro models of tumor invasion, where it significantly abrogated invasion of MCF-10A neoT cells. These data show that we have successfully explored the structure-activity relationships of nitroxoline derivatives to provide new inhibitors that could eventually lead to compounds with clinical usefulness against the deleterious effects of cathepsin B in cancer progression.